{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ransom Note"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canConstruct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #赎金信"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串：<code>ransomNote</code> 和 <code>magazine</code> ，判断 <code>ransomNote</code> 能不能由 <code>magazine</code> 里面的字符构成。</p>\n",
    "\n",
    "<p>如果可以，返回 <code>true</code> ；否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><code>magazine</code> 中的每个字符只能在 <code>ransomNote</code> 中使用一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ransomNote = \"a\", magazine = \"b\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ransomNote = \"aa\", magazine = \"ab\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ransomNote = \"aa\", magazine = \"aab\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ransomNote.length, magazine.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>ransomNote</code> 和 <code>magazine</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ransom-note](https://leetcode.cn/problems/ransom-note/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ransom-note](https://leetcode.cn/problems/ransom-note/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"a\"\\n\"b\"', '\"aa\"\\n\"ab\"', '\"aa\"\\n\"aab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        if len(ransomNote)>len(magazine):\n",
    "            return False\n",
    "      \n",
    "        dict_rans = Counter(ransomNote)\n",
    "        dict_maga = Counter(magazine)\n",
    "        for elem in dict_rans.keys():\n",
    "            if not dict_maga[elem]:\n",
    "                return False\n",
    "            elif dict_maga[elem]<dict_rans[elem]:\n",
    "                return False\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        for c in ransomNote:\n",
    "            d[c] = d.get(c, 0) - 1\n",
    "        for c in magazine:\n",
    "            if c in d:\n",
    "                d[c] += 1\n",
    "                if not d[c]:\n",
    "                    del d[c]\n",
    "        return not d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import re\n",
    "        for x in ransomNote:\n",
    "            if x in magazine:\n",
    "                magazine = re.sub(x, ' ', magazine, 1)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def decode(string):\n",
    "            ans = [0] * 26\n",
    "            for s in string:\n",
    "                ans[ord(s) - 97] += 1\n",
    "            return ans\n",
    "        \n",
    "        return all(i <= j for i, j in zip(decode(ransomNote), decode(magazine)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        magazine = list(magazine)\n",
    "        for s in ransomNote:\n",
    "            if s in magazine:\n",
    "                magazine.remove(s)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        target = list(ransomNote)\n",
    "        source = list(magazine)\n",
    "        for c in source:\n",
    "            if c in target:\n",
    "                target.remove(c)\n",
    "        if len(target) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        mag = list(magazine)\n",
    "        for i in ransomNote:\n",
    "            if i in mag:\n",
    "                mag.remove(i)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for x in ransomNote:\n",
    "            if x in magazine:\n",
    "                magazine = magazine.replace(x, '', 1)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if ransomNote == \"\":\n",
    "            return True\n",
    "        ransomNote = sorted(ransomNote)\n",
    "        magazine = sorted(magazine)\n",
    "        j = 0\n",
    "        for i in magazine:\n",
    "            if ransomNote[j] == i:\n",
    "                j += 1\n",
    "                if j >= len(ransomNote):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        r = sorted(ransomNote);\n",
    "        m = sorted(magazine);\n",
    "        if(len(m) < len(r)):\n",
    "            return False;\n",
    "        if(len(r) == 0):\n",
    "            return True;\n",
    "        l = 0;\n",
    "        for c in m:\n",
    "            if(c == r[l]):\n",
    "                l += 1;\n",
    "            if(l == len(r)):\n",
    "                return True;\n",
    "        return False;\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        for s in ransomNote:\n",
    "            if s in magazine:\n",
    "                ransomNote = ransomNote.replace(s, '', 1)\n",
    "                magazine = magazine.replace(s, '',  1)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "    \ttmp = {}\n",
    "    \tfor i in magazine:\n",
    "    \t\tif i in tmp.keys():\n",
    "    \t\t\ttmp[i] += 1\n",
    "    \t\telse:\n",
    "    \t\t\ttmp[i] = 1\n",
    "\n",
    "    \tfor i in ransomNote:\n",
    "    \t\tif i in tmp.keys():\n",
    "    \t\t\tif tmp[i] > 0:\n",
    "    \t\t\t\ttmp[i] -= 1\n",
    "    \t\t\telse:\n",
    "    \t\t\t\treturn False\n",
    "    \t\telse:\n",
    "    \t\t\treturn False\n",
    "    \treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\r\n",
    "        a,b = Counter(ransomNote),Counter(magazine)\r\n",
    "        return a&b == a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        from collections import Counter\n",
    "        hsmap1 = Counter(ransomNote)\n",
    "        hsmap2 = Counter(magazine)\n",
    "        for i in hsmap1.keys():\n",
    "            if hsmap1[i] > hsmap2[i]:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        ransom_count = collections.Counter(ransomNote)\n",
    "        magazine_count = collections.Counter(magazine)\n",
    "        return ransom_count & magazine_count == ransom_count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        dic={}\n",
    "        for i in range(len(magazine)):\n",
    "            if magazine[i] in dic:\n",
    "                dic[magazine[i]]+=1\n",
    "            else:\n",
    "                dic[magazine[i]]=1\n",
    "        for j in range(len(ransomNote)):\n",
    "            if ransomNote[j] in dic and dic[ransomNote[j]]>0:\n",
    "                dic[ransomNote[j]]-=1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        from collections import Counter\n",
    "        r,m=Counter(ransomNote),Counter(magazine)\n",
    "        for k,v in r.items():\n",
    "            if k in m and v<=m[k]:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        ransomNote_Counter = collections.Counter(ransomNote)\n",
    "        magazine_Counetr = collections.Counter(magazine)\n",
    "        for key in ransomNote_Counter:\n",
    "            if ransomNote_Counter[key] > magazine_Counetr[key]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        tmp = list(magazine)\n",
    "        for i in ransomNote:\n",
    "            if i not in tmp:\n",
    "                return False\n",
    "            if i in tmp:\n",
    "                tmp.remove(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        magazine = list(magazine)\n",
    "        for s in ransomNote:\n",
    "            if s in magazine:\n",
    "                magazine.pop(magazine.index(s))\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        if ransomNote in magazine:\n",
    "            return True\n",
    "        mag = list(magazine)\n",
    "        print(mag)\n",
    "        for i in range(len(ransomNote)):\n",
    "            if ransomNote[i] in mag:\n",
    "                mag.remove(ransomNote[i])\n",
    "                if i == len(ransomNote)-1:\n",
    "                    return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        magazine_dict = {}\n",
    "        for index, item in enumerate(magazine):\n",
    "            magazine_dict.setdefault(item, []).append(index)\n",
    "\n",
    "\n",
    "        for item in ransomNote:\n",
    "            if magazine_dict.get(item):\n",
    "                magazine_dict[item].pop()\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        for a in set(ransomNote):\n",
    "            if ransomNote.count(a) > magazine.count(a):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        for i in ransomNote:\n",
    "           if ransomNote.count(i)>magazine.count(i):\n",
    "               return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        for i in set(ransomNote):\n",
    "           if ransomNote.count(i)>magazine.count(i):\n",
    "               return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        hashtableR, hashtableM = {}, {}\n",
    "        for i in range(len(ransomNote)):\n",
    "            if ransomNote[i] not in hashtableR:\n",
    "                hashtableR[ransomNote[i]] = 1\n",
    "            else:\n",
    "                hashtableR[ransomNote[i]] += 1\n",
    "\n",
    "        for i in range(len(magazine)):\n",
    "            if magazine[i] not in hashtableM:\n",
    "                hashtableM[magazine[i]] = 1\n",
    "            else:\n",
    "                hashtableM[magazine[i]] += 1\n",
    "\n",
    "        print(hashtableR, hashtableM)\n",
    "        for key, value in hashtableR.items():\n",
    "            if key not in hashtableM:\n",
    "                return False\n",
    "            if value > hashtableM[key]:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        count = 0\n",
    "        temp = list(magazine)\n",
    "        for i in ransomNote:\n",
    "            if i in temp:\n",
    "                count += 1\n",
    "                temp.remove(str(i))\n",
    "\n",
    "        if count == len(ransomNote):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        # magazine = list(magazine)\n",
    "        # ransomNote = list(ransomNote)\n",
    "        # count = 0\n",
    "        # for i in range(len(ransomNote)):\n",
    "        #     for j in range(len(magazine)):\n",
    "        #         if ransomNote[i] == magazine[j]:\n",
    "        #             magazine[j] = \"*\"\n",
    "        #             count+=1\n",
    "        #             break\n",
    "        # if count == len(ransomNote):\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "        \n",
    "        hashdict = {}\n",
    "        for i in magazine:\n",
    "            if i not in hashdict:\n",
    "                hashdict[i] = 1\n",
    "            else:\n",
    "                hashdict[i] +=1\n",
    "        result = True\n",
    "        for i in ransomNote:\n",
    "            if i in hashdict and hashdict[i]>=1:\n",
    "                hashdict[i] -= 1\n",
    "            else:\n",
    "                result = False\n",
    "                break\n",
    "        return result\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        s = dict()\n",
    "        for i in ransomNote:\n",
    "            s[i] = s.get(i,0)+1\n",
    "        \n",
    "        for i in magazine:\n",
    "            s[i] = s.get(i,0)-1\n",
    "        \n",
    "        for i in s.values():\n",
    "            if i > 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        a={}\n",
    "        b={}\n",
    "        for i in ransomNote:\n",
    "            if i in a:\n",
    "                a[i]+=1\n",
    "            else:\n",
    "                a[i]=1\n",
    "        for j in magazine:\n",
    "            if j in b:\n",
    "                b[j]+=1\n",
    "            else:\n",
    "                b[j]=1\n",
    "        m=0\n",
    "        for i in a.keys():\n",
    "            if i not in b:\n",
    "                break\n",
    "            elif b[i]>=a[i]:\n",
    "                m+=1\n",
    "            else:\n",
    "                break\n",
    "        if m==len(a):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, ransomNote: str, magazine: str) -> bool:\n",
    "        # 统计magazine中的次数\n",
    "        dict1 = {}\n",
    "        for i in magazine:\n",
    "            if i not in dict1:\n",
    "                dict1[i] = 1\n",
    "            else:\n",
    "                dict1[i] = dict1[i] + 1\n",
    "        # 如果次数为0，或者找不到则返回False\n",
    "        for i in ransomNote:\n",
    "            if i in dict1:\n",
    "                dict1[i] = dict1[i] - 1\n",
    "                if dict1[i] < 0:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
